package com.shr.code_interview;

import java.util.HashMap;
import java.util.Map;

public class Solution_39 {
    public int MoreThanHalfNum_Solution(int [] array) {
    	Map<Integer, Integer> map = new HashMap<>() ;
        for(int i = 0; i< array.length;i++)
        	map.put(array[i], 0) ;
        for(int i = 0;i<array.length;i++)
        	map.put(array[i], 1 + map.get(array[i])) ;
        for(int key : map.keySet()){
        	if(map.get(key) > array.length / 2)
        		return key;
        }
        return 0 ;
        	
    }
}
